Images, especially multivalued images, contain a great amount of information that presents a problem when the images are stored and transmitted. At the time of such storage and transmission, therefore, use is made of highly efficient encoding that reduces the amount of information by eliminating image redundancy or altering the content of an image but only to such an extent that will not allow any decline in image quality to be readily distinguishable visually.
For example, with the JPEG scheme recommended by the ISO and ITU-T as an international standard for the encoding of still images, image data is converted to DCT (Direct Cosine Transform) coefficients by applying the DCT to the image data on a per-block (8×8 pixel) basis, the coefficients are quantized and then entropy encoding is applied to thereby compress the image data. Since the DCT and quantization is applied block by block, there are instances where so-called “block distortion” can be seen at the block boundaries in the decoded images.
JPEG 2000 is being considered as a new international standard for encoding still images. In JPEG 2000, a wavelet transform has been proposed as one type of pre-processing executed prior to quantization. With the wavelet transform, processing is not executed on a per-block basis as with the present JPEG scheme; rather, the input data is processing in continuous fashion. As a result, a feature of this approach is that degradation of the decoded image is not easy to recognize visually.
A discrete wavelet transform used in JPEG 2000 is positioned as filter processing means that divides image data into low- and high-frequency components. Filter processing usually is implemented by a convolution operation between filter coefficients and image data. However, a method based upon a lifting scheme can be applied, besides the convolution operation, to the following discrete wavelet transform used in JPEG 2000:                Daubecheis 9/7 Filter (referred to as a “9×7 filter” below”)        Daubecheis 5/3 Filter (referred to as a “5×3 filter” below”)        
The lifting scheme will now be described.
<Description of Lifting Scheme>
FIG. 1 illustrates the basic implementation of a forward lifting scheme and FIG. 2 the basic implementation of a reverse lifting scheme. In FIG. 1, p and u are referred to as “lifting coefficients”. FIG. 3 illustrates the filter coefficients of a 5×3 filter and FIG. 4 the lifting coefficients of the 5×3 filter.
The operation shown in FIG. 1 will be described based upon the lifting coefficientsp=(−1, −1)/2u=(1, 1)/4illustrated in FIG. 4.
In FIG. 1, X represents input image data, which enter in the order X0, X1, X2, X3, X4, X5 . . . , as illustrated in FIG. 1. The data is classified into pixel data of an even-numbered sequence and pixel data of an odd-numbered sequence starting from the beginning of the input image.
The odd-sequence pixel data (X1, X3, X5, X7 . . . ) is generated by a downsampling unit 105, which downsamples the input image data every other pixel starting from the beginning of the data.
The even-sequence pixel data (X0, X2, X4, X6 . . . ) is generated by delaying the image data by one pixel using a delay unit 101 and then downsampling the single-pixel-delayed image data every other pixel using a downsampling unit 103.
Since the two downsampling units operate at the same timing, the pixel data of the two sequences having different downsampling phases can be generated by downsampling the data delayed by one pixel in the delay unit 101 and the undelayed input image data.
A multiplier 107 multiplies the even-sequence pixel data by the lifting coefficient p, and an adder 109 adds the product to the odd-sequence pixel data to calculate a transform coefficient X′o (X′1, X′3, X′5, X′7 . . . ) on the high-frequency side.
The processing for multiplying by the lifting coefficient and adding on the product is processing constituting a single unit in the lifting scheme and is referred to as a “lifting step”.
The lifting coefficient p is vector data having two components. The pixel data of two successive even sequences is multiplied by each component (coefficient value), and the sum of the two products becomes the result of multiplication by the lifting coefficient p.
Multiplication by the lifting coefficient u in a multiplier 111 is performed in similar fashion. What is multiplied here is the just calculated transform coefficient X′o on the high-frequency side. The product is added to the pixel data of the even sequence by an adder 113, whereby a transform coefficient X′e (X′0, X′2, X′4, X′6 . . . ) on the low-frequency side is found.
If the above-described processing is expressed concretely in the form of equations, we have the following:
(transform coefficient on high-frequency side):X′2n+1=X2n+1+(−X2n−X2n+2)/2  (1)
(transform coefficient on low-frequency side):X′2n=X2n+(X′2n−1+X′2n+1)/4  (2)
The above processing is executed once in the horizontal direction and once in the vertical direction, and these two executions constitute one set. A discrete wavelet transform is implemented by repeating several sets of the above processing with regard to the low-frequency components. This is followed by performing quantization and entropy encoding to finally generate the encoded image data. On the decoding side, on the other hand, this processing is executed in reverse to reconstruct the original image.
A series of processing operations from the encoding side to the decoding side will now be described. To simplify the description, quantization and entropy encoding will be omitted. Further, let D represent the input image data, DWT the discrete wavelet transform, and IDWT an inverse discrete wavelet transform.
Processing is executed as follows:D→DWT→IDWT→D
This signifies how the original image D can be reconstructed. Specifically, the transformation process can be thought of as being reversible if viewed mathematically. However, if this is packaged in the form of circuitry or software, “reversibility” is difficult to achieve. The reason is as follows:
An item of original image data generally is an integer. When the above-described filter processing is executed one time, however, data of floating-point type is obtained and the decimal fraction gives rise to, e.g., three bits. With two-dimensional filter processing, the processing is executed twice, namely once in the horizontal direction and once in the vertical direction, as mentioned above. This means that a 6-bit decimal fraction will be produced unless processing for rounding the decimal is executed during the course of filter processing. Furthermore, if filter processing is executed recursively again and again, the decimal fraction increases in proportion.
If a decimal fraction of six bits or more is left as is, the amount of data will increase. Usually, therefore, rounding is executed to obtain an integer and then the integer is saved. When image data is compressed, integerization or quantization is carried out so that the filtered data is reduced further.
Since information will be lost if the result of filter processing is rounded or quantized, data identical with the original image data will not be reconstructed even if filter processing in the reverse direction (processing on the decoding side) is executed. “Reversibility” will not be achieved, therefore, when the above is packaged in the form of circuitry or software.
The foregoing is filter processing in the forward direction. Processing in the reverse direction will now be described.
The reverse lifting scheme, which is shown in FIG. 2, employs processing that resembles that of the forward direction. If the processing is expressed in the form of equations, we have the following:
(pixels of even-numbered sequence):X2n=X2n−(X′2n−1+X′2n+1)/4  (3)
(pixels of odd-numbered sequence):X2n+1=X′2n+1−(−X2n−X2n+2)/4  (4)This differs from processing in the forward direction in the following three points:                the order of the lifting coefficients used in the lifting step performed twice is reversed;        the result obtained by multiplication by the lifting coefficients is subtracted not added; and        a zero-insertion unit is used after lifting instead of the downsampling unit.        
Units 209 and 213 in FIG. 2 are subtractors for performing the above-mentioned subtraction, and units 203 and 205 are units for performing zero insertion.
Pixel data of the odd sequence that has undergone zero insertion is delayed one pixel by a delay unit 201 in order to achieve matching of phases. As a result, non-zero valid pixel data is obtained alternatingly from the sides of the even and odd sequences. Data that is the result of subjecting the original image data to forward and reverse filter processing can be obtained by combining the non-zero valid pixel data into a single sequence.
If the number of filter taps is changed, the number of lifting coefficients and the number of lifting step will change. With the 9×7 filter, for example, the lifting step is performed four times.
When the lifting scheme is used, the operation for the summing of products can be implemented fewer times in comparison with convolution processing. As a result, implementation is made more efficient and, moreover, an integer-type reversible transform, described below, becomes possible.
<Description of Reversible Transform>
As described above, the transform is reversible mathematically but is not necessarily reversible when packaged (referred to as “packaged reversibility” below). This will now be described in greater detail.
If broadly defined, a reversible transform is a transform whereby the original data can be reconstructed perfectly if transform coefficient data obtained by filter processing (transform processing) in the forward direction is subjected to filter processing in the reverse direction. This property of the reversible transform is referred to as “reversibility”. A transform said to be reversible mathematically falls within the scope of this definition. More specifically, a transformation matrix is represented by a normal orthogonal matrix, as in a DCT, and there are filters in which the operation is performed by the above-described lifting scheme. In a broadly defined reversible transform, error accumulates owing to iteration processing if error is large at the time of real-number calculation, and therefore the original data may not be reconstructed even if the transform is performed in reverse. This means that computation bit length needs to be taken into consideration. In order to contrast the meaning of this with the integer-type reversible transform described below, the broadly defined reversible transform shall be referred to as a “real-number-type reversible transform” below.
In a real-number-type reversible transform, the overall amount of data (number of data items×bit length) that must be retained in order to possess reversibility increases. If the transform is executed recursively over and over, the amount of data increases until it is many times the amount of original data. In general, therefore, if transformation processing is executed for the purpose of data compression, reversibility is sacrificed and non-reversible compression is carried out. JPEG, H261, MPEG1/2/4, etc., which are employed in the compression of image data (still and moving images) are typical of such processing.
By contrast, an integer-type reversible transform is transform processing whereby the original data is reconstructed by reversible transform processing while the integers in data after execution of filter processing are identical with those of the input data. (There are also cases where if an input is fixed-point data, then the output also is the same fixed-point data.) This reversible transform is not one that can be implemented if the result of the above-mentioned real-number-type reversible transform is simply rounded to achieve integerization; it is a transform that can be implemented by executing the rounding processing for integerization in each lifting step, as will be described later. This shall be referred to as a “narrowly defined reversible transform”. When the simple term “reversible transform” (reversible filter) is used below, this will indicate the narrowly defined reversible transform, namely the integer-type reversible transform.
In order to indicate that a certain transform is reversible, it is necessary to indicate the forward reversible transform and its corresponding reverse reversible transform in the form of a pair.
In order to implement reversible filter processing using the lifting scheme, rounding is executed in each lifting step, as mentioned above. More specifically, in each lifting step, rounding processing is executed before the result obtained by lifting-coefficient multiplication is added on or subtracted.
Reversibility will now be described taking a 5×3 filter that is capable of executing a reversible transform (this shall be referred to as a “reversible 5×3 filter”) as an example. In order to render the description, FIG. 5 illustrates a processing system in which a reversible transform in the reverse direction is executed immediately after a reversible transform in the forward direction.
In FIG. 5, numerals 501, 503, 505, 507 represent floor-function arithmetic units for extracting an integer that will not exceed input data, and numerals 502, 504 denote adding units for adding 0.5 to data obtained by multiplication by lifting coefficients. The other units are exactly the same as those having like reference numerals used in FIGS. 1 and 2. Only integer data is inputted to the adders and subtractors in FIG. 5, and naturally the outputs thereof also are integer data. Such a lifting operation is referred to as “integer lifting” and is used to implement a reversible transform.
That the aforesaid filter processing (transform processing) is reversible will be demonstrated by describing that the result of processing image data (an integer), which has entered from the left side of FIG. 5, by a forward filter processor 540 and then processing the output of the processor 540 by a reverse filter processor 550 is exactly the same as the original input.
First, it should be noted that the inputs to the two adders and two subtractors in FIG. 5 are all integers, and that the outputs thereof also are integers.
The purpose of this description will be to indicate that an even-numbered pixel sequence and an odd-numbered pixel sequence before and after filter processing are equal to each other using a property (c) below after it is described that properties (a), (b) below hold true.
(a) The output of the floor-function arithmetic unit 503 in the forward filter processor 540 and the output of the floor-function arithmetic unit 505 in the reverse filter processor 550 are equal;
(b) the output of the floor-function arithmetic unit 501 in the forward filter processor 540 and the output of the floor-function arithmetic unit 507 in the reverse filter processor 550 are equal; and
(c) if a value identical with that added is subtracted, then the original value that prevailed prior to addition will be reconstructed.
Multipliers 111 and 211 multiply by the same lifting coefficient u, and the data sequence that undergoes multiplication also is the same transform coefficient X′o on the high-frequency side. Accordingly, the outputs of these two multipliers are equal. The outputs have 0.5 added to them by the adding units 502, 504, respectively, and naturally the results obtained via the floor-function arithmetic units 503, 505 also are equal. Thus, it can be said that property (a) holds true. If property (c) is now utilized, it can be said that the even pixel sequence Xe input to the adder 113 and the even pixel sequence output from the subtractor 213 are equal.
Next, multipliers 102 and 207 also multiply by the same lifting coefficient p, and the data sequence that undergoes multiplication also is the above-mentioned even pixel sequence Xe. Accordingly, the outputs of these two multipliers are equal, and naturally the results obtained by processing these outputs by the floor-function arithmetic units 501, 507, respectively, also are equal. Thus, it can be said that property (b) holds true. If property (c) is now utilized, it can be said that the odd pixel sequence Xo input to the adder 109 and the odd pixel sequence output from the subtractor 209 are equal. As a result, the forward filter processor 540 and reverse filter processor 550 illustrated in FIG. 5 can be construed to be reversible.
The output of the forward filter processor 540 need not be subjected to rounding for integerization because it is already an integer; the output of this integer can be input directly to the reverse filter processor 550. If the quantization step is set to “1” by quantization processing used at the time of data compression, no information will be lost due to this quantization processing and, hence, reversible compression can be carried out. If the quantization step is set to be larger than “1”, however, loss of information will occur. This means that although the compression rate rises, compression can no longer be performed reversibly.
A reversible transform is made possible by using the lifting scheme in the manner set forth above. The relationship between types of filters and computation techniques for implementing these filter may be summarized as follows:                filter processing with a finite impulse response can be implemented by a convolution operation;        some filter processing can be implemented by a lifting scheme (some cannot);        a real-number-type filter that can be implemented by the lifting scheme is capable of a reversible transform; and        an integer-type reversible filter can be implemented by making the lifting operation one of the integer type in the above-mentioned real-number-type reversible filter.        
Accordingly, though almost all filter processing can be realized by a convolution operation, integer-type reversible filter processing cannot be implemented using a convolution operation. This means that in a case where it is necessary to have both the function of filter processing, which cannot be implemented with the lifting scheme (it can only be implemented by a convolution operation), and the function of integer-type reversible filter processing, this must be realized by separate processors (circuits).
Further, since it is necessary to perform the integer-type lifting operation when integer-type reversible filter processing is executed, real-number-type filter processing cannot be executed at the same time and, hence, it is not possible to obtain the results of both integer-type and real-number-type filter processing at the same time.
Thus, as set forth above, reversible filter processing has not been achievable heretofore by using a convolution operation. Accordingly, if it is necessary to have both the function of filter processing, which can only be implemented by a convolution operation, and the function of reversible filter processing, separate processors (circuits) must be used, the filter processing apparatus is large in size and the apparatus cannot be constructed at low cost.
Further, integer-type reversible filter processing and real-number-type filter processing cannot be executed simultaneously and the results of both integer-type and real-number-type filter processing cannot be obtained simultaneously. In order to manufacture a chip having both these functions, two types of filters must be packaged in the chip.